package com.chenxys.algorithm.newbie;

import java.util.Arrays;

/**
 * <p>
 *      二分法：
 *          有序数组中找到 <= num 最右的位置
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.newbie
 * @date 12/25/23 11:33 PM
 * @Copyright ©
 */
public class DichotomyV3 {
    /**
     * <p>
     *     找到数组中 <=num 最左的位置
     * </p>
     * @param sortedArr 有序数组
     * @param num 待判断的数
     * @return 最右位置
     */
    public static int mostRightNoLessIndex(int[] sortedArr, int num){
        if (sortedArr == null || sortedArr.length == 0) return -1;
        int L = 0;
        int R = sortedArr.length - 1;
        int ans = -1;// 不存在这样的数
        while (L <= R) {
            // ans 更新
            // 中点
            int mid = (L + R) / 2;
            if (sortedArr[mid] <= num){
                ans = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return ans;
    }


    /**
     * <p>
     *     找到数组中 <=num 最右的位置
     * </p>
     * @param sortedArr 有序数组
     * @param num 待判断数字
     * @return 最右位置
     */
    public static int test(int[] sortedArr, int num){
        for (int i = sortedArr.length - 1; i >= 0; i--) {
            if (sortedArr[i] <= num) return i;
        }
        return -1;
    }

    /**
     * <p>
     *     生成随机数组
     * </p>
     * @param maxSize 数组最大长度
     * @param maxValue 数组最大值
     * @return 随机数组
     */
    public static int[] generateRandomArray(int maxSize, int maxValue){
        int[] arr = new  int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random() - (int) (maxValue * Math.random()));
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTimes = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            // 保证数组有序
            Arrays.sort(arr);
            // 待查询的数
            int value = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue) * Math.random());
            if (test(arr, value) != mostRightNoLessIndex(arr, value)) {
                System.out.println("error!!!");
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }
}
